class Solution:
    def divide(self, a: int, b: int) -> int:
        if a == 0:
            return 0

        # 处理负号的问题
        sign = 1 if a * b > 0 else -1
        a, b = abs(a), abs(b)

        ans = 0

        while a >= b:
            # 寻找当前最大的二进制位
            c = b
            bit = 1
            while a > c + c:
                c += c
                bit += bit

            # 减去当前最大的二进制位
            a -= c
            ans += bit

        if sign == 1:
            return min(ans, 2147483647)
        else:
            return - ans


if __name__ == "__main__":
    print(Solution().divide(15, 2))  # 7
    print(Solution().divide(7, -3))  # -2
    print(Solution().divide(0, 1))  # 0
    print(Solution().divide(1, 1))  # 1
